package leetcode.editor.week.week305;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution6138 {
    // 300.最长递增子序列的变种，需要优化，不然会超时
    // https://leetcode.cn/problems/longest-ideal-subsequence/solution/by-lfool-afr2/
    public int longestIdealString(String s, int k) {
        int n = s.length();
        Map<Character, Integer> map = new HashMap<>();  // 记录以某个字母结尾的最长子序列的长度
        char[] arr = s.toCharArray();
        int[] dp = new int[n];
        int res = 0;
        Arrays.fill(dp, 1);

        for (int i = 0; i < arr.length; i++) {
            char cur = arr[i];
            // 在k的范围中搜索
            for (int j = 0; j <= k; j++) {
                // 比cur小的
                char t1 = (char) (cur - j);
                // 比cur大
                char t2 = (char) (cur + j);

                // 判断在map中能否找到
                if (map.containsKey(t1)) {
                    dp[i] = Math.max(dp[i], map.get(t1) + 1);
                }

                if (map.containsKey(t2)) {
                    dp[i] = Math.max(dp[i], map.get(t2) + 1);
                }
            }
            map.put(cur, dp[i]);
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}
